package org.shj.suanfa

import scala.collection.mutable.ArrayBuffer

/**
 * 给定一个长度为N的非空整数数组，找出使数组所有元素均相等的最少操作数。其中一次操作是指
 * 将其中N-1个数(不一定连续)加上1
 * 如： [1, 2, 3] 需要最少3次
 * [1, 2, 3] -> [2,3,3] -> [3,4,3] -> [4,4,4]
 * 
 * 自己的解题思路：
 * 1. 按从大到小排序，除了第一个元素之外，都 +1
 * 2. 判断是否所有元素都相等，如果不是，则循环第一步
 * 
 * 更好的解题思路：
 * 将N-1个数+1，相当于将所有数都加+1，再将其中一个数减1
 * 将所有数都 +1，这一步对于各个数之间的差值没有任何影响，故可以忽略这一步
 * 那么问题就变成每次选一个数减1来达到目标的最小次数
 * 要使次数最小，而且每次只能将一个元素 -1，故应把所有数都减到与最小值
 * 
 */
object MinOps {
  def main(args: Array[String]): Unit = {
    val arr = ArrayBuffer(3, 1, 2)
    method1(arr)
    method2(arr)
  }
  
  def method1(input: ArrayBuffer[Int]){
    var arr = input
    var ele = arr(0)    
    var cnt = 0
    while(!arr.forall(x => x == ele)){
      arr = arr.sortWith(_ > _)
      ele = arr.head
      var tmp = ArrayBuffer[Int]()
      for(item <- arr.tail){
        tmp += item
      }
      arr = tmp
      cnt += 1
    }
    println(cnt)
  }
  
  def method2(arr: ArrayBuffer[Int]){
    val min = arr.min
    val sum = arr.sum
    val cnt = sum - arr.length*min
    println(cnt)
  }
}